using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Linq.Dynamic;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0005. 最长回文子串")]
    public class No0005_LongestPalindrome : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(LongestPalindrome, (string)null, string.Empty);
            Assert.TestExe(LongestPalindrome, "ccc", "ccc");
            Assert.TestExe(LongestPalindrome, "bb", "bb");
            Assert.TestExe(LongestPalindrome, "a", "a");
            Assert.TestExe(LongestPalindrome, "ab", "a", "b");
            Assert.TestExe(LongestPalindrome, "babad", "bab", "aba");
            Assert.TestExe(LongestPalindrome, "cbbd", "bb");
        }

        public string LongestPalindrome(string s)
        {
            if (s == null || s.Length < 1)
            {
                return string.Empty;
            }
            int start = 0;
            int end = 0;
            for (int i = 0; i < s.Length; i++)
            {
                int len1 = expandAroundCenter(s, i, i);
                int len2 = expandAroundCenter(s, i, i + 1);
                int len = Math.Max(len1, len2);
                if (len > end - start)
                {
                    start = i - (len - 1) / 2;
                    end = i + len / 2;
                }
            }
            return s.Substring(start, end - start + 1);
        }

        private int expandAroundCenter(string s, int left, int right)
        {
            while (0 <= left && right < s.Length && s[left] == s[right])
            {
                left--;
                right++;
            }
            return right - left - 1;
        }

        public string LongestPalindrome2(string s)
        {
            if (s == null || s.Length < 1)
            {
                return string.Empty;
            }
            const string sc = "#";
            s = sc + string.Join(sc, s.ToArray()) + sc;
            int start = 0;
            int end = 0;
            for (int i = 0; i < s.Length; i++)
            {
                int left = i;
                int right = i;
                while (0 <= left && right < s.Length && s[left] == s[right])
                {
                    left--;
                    right++;
                }
                int len = right - left - 1;
                if (len > end - start)
                {
                    start = i - (len - 1) / 2;
                    end = i + len / 2;
                }
            }
            string result = s.Substring(start + 1, end - start);
            char[] chars = new char[result.Length / 2];
            for (int i = 0; i < result.Length; i++)
            {
                if (i != 0 && (i & 1) == 1)
                    continue;
                chars[i / 2] = result[i];
            }
            return string.Join("", chars);
        }
    }
}
